Link to this headingDiffie–Hellman (DHКЕ)

• It does not authenticate and is vulnerable to MITM attacks
• Uses Discrete Log to make a shared key
  • Uses the property that (g^a)^b mod p = (g^b)^a mod p
• Uses the properity that finding the secret a from g^a mod p is hard

Link to this headingProtocol Example

1. User1 and User2 use two public integers:
   • P which is the modulus (Where P is prime)
   • G which is the base (Where G is repetitively prime to P)
2. For Example let p = 23 and g = 5. (These are usually Hard-coded)
3. User1 chooses a secret integer a (e.g. a = 4)
   • 5^4 mod 23 = 4 (This Output is public Data A)
4. User2 chooses a secret integer a (e.g. a = 3)
   • 5^3 mod 23 = 10 (This Output is public Data B)
5. Each User exchanges the output to each other
6. User1 Computes the shared secret
   • 10^4 mod 23 = 18
7. User2 Computes the shared secret
   • 4^3 mod 23 = 18

In the most common implementation of DHKE (following the RFC 3526) the base is g = 2 and the modulus p is a large prime number (1536 … 8192 bits).

Link to this headingImplementation

Link to this headingAttacks

https://kel.bz/post/hnp/

Link to this headingSmall Subgroup Confinement Attack

By choosing a value for k where k = (prime_mod-1)/w and w is the prime of the Small Subgroup. This makes the secret key to be in the small group and can be found through an exhaustive search.

1. User1 calculates her public key as A = g^(x*a) and sends it over the wire
2. The MITM captures A and replaces it with A^k
3. User2 calculates his public key as B = g^(y*b) and sends it over the wire
   • User2 calculates the shared private key as S = (A^k)^b
4. The MITM captures B and replaces it with B^k
5. User2 calculates the shared private key as S = (B^k)^a

Proof

Example Code:

Link to this headingSimple Brute Force

Link to this headingBaby Step Giant Step

• O(sqrt(n))
• Takes alot of memory to run

Any secret can be expressed as x = i*m + j

\begin{aligned}
y &= g^x \pmod{p} \\
 &= g^{i*m + j} \pmod{p} \\
 &= g^{i*m + j} \pmod{p} \\
 &= g^{i*m} * g^j \pmod{p} \\
\end{aligned}

\\~\\

y * g^{-i*m} = g^j \pmod{p}

import secrets
import math

def generate_key_pair(prime=((1 << 1024) - 1093337), g=7):
	#generate a 1024 bit prime number for the Mod
	#prime_mod = generate_probable_prime(1024)
	prime_mod = prime

	#Genreate Secret Exponent
	secret_exp = 0
	while secret_exp < 2:
		secret_exp = secrets.randbelow(prime_mod-2)
	generator = g

	#Generate the Transmit key A = G^x % P
	transmit_key = pow(generator, secret_exp, prime_mod)

	return {"generator":generator, "prime_mod":prime_mod, "transmit_key": transmit_key}, {"generator":generator, "prime_mod":prime_mod, "secret_exp": secret_exp} 


def bsgs_dlp(g, y, p):
	mod_size = len(bin(p-1)[2:])

	print("[+] Using BSGS algorithm to solve DLP")
	print("[+] Modulus size: " + str(mod_size) + ". Warning! BSGS not space efficient\n")

	m = math.ceil(math.sqrt(p-1))

	# Make a lookup table for 1,j
	lookup_table = {pow(g, j, p): j for j in range(m)}

	# Precompute g^(-m) so it is easy to substitute in every lookup
	c = pow(g, m*(p-2), p)

	# Giant Steps
	for i in range(m):
		#Calculate y*g^(-m*i) = y * g^-m * g^i = y * c * g^i = y * c ^ i
		temp = (y*pow(c, i, p)) % p

		#Check if value is in lookup table and get the index
		if temp in lookup_table:
			# x found
			return i*m + lookup_table[temp]
	return None

  

if __name__ == '__main__':
	#Generate User1 Keys
	user1_public_key, user1_private_key = generate_key_pair(prime=3875972899)
	#user1_public_key, user1_private_key = generate_key_pair(prime=13091037018084742351)


	test = bsgs_dlp(user1_public_key["generator"], user1_public_key["transmit_key"], user1_public_key["prime_mod"])

	assert user1_private_key["secret_exp"] == test
	print(f"Found exponent: {test}")
#[+] Using BSGS algorithm to solve DLP
#[+] Modulus size: 32. Warning! BSGS not space efficient

#Found exponent: 3238504688
#[Finished in 269ms]
Link to this headingPollards Rho

O(sqrt(n))
Fastest for prime orders

f"""
This is a simple, yet straight forward implementation of Pollard's rho algorithm for discrete logarithms
It computes X such that G^X = H mod P.

p does not need to be a safe prime.
"""
from gmpy2 import invert, gcd


def xab(x, a, b, params):
	"""
	Pollard Step
	:param x:
	:param a:
	:param b:
	:return:
	"""
	G, H, P, Q = params
	sub = x % 3 # Subsets

	if sub == 0:
		x = x*G % P
		a = (a+1) % Q
	elif sub == 1:
		x = x*H % P
		b = (b+1) % Q
	else:
		# sub == 2:
		x = x*x % P
		a = a*2 % Q
		b = b*2 % Q

	return x, a, b


def pollard(G, H, P):

	# P: prime
	# H:
	# G: generator
	Q = (P - 1)  # multiplicative sub group order

	x, a, b = 1, 0, 0
	X, A, B = x, a, b

	# for i in range(1, P):
	while True:
		# Hedgehog
		x, a, b = xab(x, a, b, (G, H, P, Q))

		# Hare
		X, A, B = xab(X, A, B, (G, H, P, Q))
		X, A, B = xab(X, A, B, (G, H, P, Q))

		if x == X:
			break

	num = a-A
	denum = B-b

	# It is necessary to compute the inverse to properly compute the fraction mod q
	# find gcd before solving linear equation denum*res = num mod Q
	gcdz = gcd(num, denum, Q)
	# print(f'gcds = {gcdz}')
	if gcdz == 1:  # standard solution
		res = invert(denum, Q)*num % Q  # divm(num, denum, Q)  # (inverse(denom, Q) * nom) % Q
	else:
		# needs a little bit more work
		# divide by gcd
		modz = Q//gcdz
		num = num//gcdz
		denum = denum//gcdz

		# baseline solution
		res0 = invert(denum, modz)*num % modz
		# check in solutions of the shape (denum/gcd)*res = (num/gcd) mod (Q/gcd) + k * (Q/gcd) (k in [0, gcd[) 
		for k in range(gcdz):
			res = res0+k*modz
			if verify(G, H, P, res):
				break
	return res


def verify(g, h, p, x):
	"""
	Verifies a given set of g, h, p and x
	:param g: Generator
	:param h:
	:param p: Prime
	:param x: Computed X
	:return:
	"""
	return pow(g, x, p) == h



import secrets

def generate_key_pair(prime=((1 << 1024) - 1093337), g=7):
	#generate a 1024 bit prime number for the Mod
	#prime_mod = generate_probable_prime(1024)
	prime_mod = prime

	#Generate Secret Exponent
	secret_exp = 0
	while secret_exp < 2:
		secret_exp = secrets.randbelow(prime_mod-2)
	generator = g

	#Generate the Transmit key A = G^x % P
	transmit_key = pow(generator, secret_exp, prime_mod)

	return {"generator":generator, "prime_mod":prime_mod, "transmit_key": transmit_key}, {"generator":generator, "prime_mod":prime_mod, "secret_exp": secret_exp} 


if __name__ == '__main__':

	#user1_public_key, user1_private_key = generate_key_pair(prime=3875972899)
	user1_public_key, user1_private_key = generate_key_pair(prime=13091037018084742351)


	test = pollard(user1_public_key["generator"], user1_public_key["transmit_key"], user1_public_key["prime_mod"])
	print(f"Found Possible answer: {test}")

	print("Validates: ", verify(user1_public_key["generator"], user1_public_key["transmit_key"], user1_public_key["prime_mod"], test))

#Found Possible answer: 6244664414481744603
#Validates:  True
#[Finished in 1461.2s]
Link to this headingPollards Kangaroo

O(sqrt(b-a))
can only be used when know some information about one of the private keys

Link to this headingPolhig-Hellman

O(sqrt(p*))
Can be used when n is factorable into many small primes

https://github.com/ashutosh1206/Crypton/tree/master/Discrete-Logarithm-Problem/Algo-Pohlig-Hellman
Link to this headingCyclic Groups
Link to this headingTelegram Implementation
The Server sends a nonce with the Key Derivation. This Nonce can be used to manipulate the output of the shared key.

Making it possible for the Server to manipulate the keys for each user.
Source
Key Derivation with a Nonce?:
(g^a)^b mod p XOR nonce